#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 递归归并
void MergeSort(int* a, int* tem, int left, int right)
{
	if (left >= right)
		return;
	int mid = left + (right - left) / 2;

	// 把递归区间分成两份
	MergeSort(a, tem, left, mid);
	MergeSort(a, tem, mid + 1, right);

	// 把归并区间分为 [begin,mid] [mid + 1,end]
	int begin = left, count = left, end = mid + 1;
	// 用双指针将正确的值放到tem数组中
	while (begin <= mid && end <= right)
	{
		if (a[begin] >= a[end])    // 后面的值插入其中
			tem[count++] = a[end++];
		else                       // 前面的值插入其中
			tem[count++] = a[begin++];
	}
	while (begin <= mid)
		tem[count++] = a[begin++];
	while (end <= right)
		tem[count++] = a[end++];
	// 再把tem数组中的数据拷到a数组中
	memcpy(a + left, tem + left, sizeof(int) * (count - left));
}
#define N 50
// 非递归归并 (循环)
void MergeSortNonR(int* a, int left, int right)
{
	int* tem = (int*)malloc(sizeof(int) * N);

	int gap = 1;
	while (gap < right)
	{
		// 每次两组同时归并 所以 i 每次增加 2 倍的gap
		for (int i = 0; i < right; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = end1 + 1, end2 = i + 2 * gap - 1;
			if (end1 >= right || begin2 >= right)
				break;
			if (end2 >= right)
				end2 = right - 1;
			int count = i;
			// 归并过程
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
					tem[count++] = a[begin1++];
				else
					tem[count++] = a[begin2++];
			}
			while (begin1 <= end1)
				tem[count++] = a[begin1++];
			while (begin2 <= end2)
				tem[count++] = a[begin2++];
			memcpy(a + i, tem + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}


	free(tem);
	tem = NULL;
}

void Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}

void test_MergeSort()
{
	int* tem = (int*)malloc(sizeof(int) * N);
	srand((unsigned int)time(0));
	int arr[N] = { 0 };
	for (int i = 0; i < N; i++)
	{
		arr[i] = rand() % 200 + i;
	}
	//MergeSort(arr, tem, 0, N - 1);
	MergeSortNonR(arr, 0, N);
	Print(arr, N);

	free(tem);
	tem = NULL;
}

int main()
{
	int arr[10] = { 7,8,5,4,6,9,2,1,3,0 };
	int* tem = (int*)malloc(sizeof(int) * 10);


	//MergeSort(arr, tem, 0, 9);
	//MergeSortNonR(arr, 0, 10);


	test_MergeSort();
	//Print(arr, 10);


	free(tem);
	tem = NULL;
	return 0;
}